package com.sfx.算法专题.动态规划.完全背包;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:<a href="https://leetcode.cn/problems/coin-change/description/">...</a>
 * User: sfx
 * Date: 2023-07-16
 * Time: 19:39
 */
public class Code_2_coinChange {
    static class Solution {
        public int coinChange(int[] coins, int amount) {
            //1.硬币任意选择,不超过总金额j的最小硬币个数为dp[j]
            int[] dp = new int[amount+1];
            //2.状态转移方程为 :
            //对于第i个硬币你选还是不选
            //                  不选    选择
            // dp[j] = Math.min(dp[j],dp[j-coins[i]] + 1)
            //3.dp数组初始化
            //dp[0][0] = 0;
            //dp[0][j] = 0;
            //dp[i][0] = 0;
            //因为要求min我们全部初始化为最大值
            Arrays.fill(dp,Integer.MAX_VALUE);
            dp[0] = 0;
            for (int coin : coins) {
                for (int j = coin; j <= amount; ++j) {
                    if (dp[j - coin] != Integer.MAX_VALUE) {
                        dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                    }
                }
            }
            return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
        }
    }
}
